Cram (game)
Cram is a mathematical game played on a sheet of graph paper (or any type of grid). It is the impartial version of Domineering and the only difference in the rules is that players may place their dominoes in either orientation, but it results in a very different game. It has been called by many names, including "plugg" by Geoffrey Mott-Smith, and "dots-and-pairs". Cram was popularized by Martin Gardner in Scientific American.[1]
Rules
[edit]The game is played on a sheet of graph paper, with any set of designs traced out. It is most commonly played on rectangular board like a 6×6 square or a checkerboard, but it can also be played on an entirely irregular polygon or a cylindrical board.
Two players have a collection of dominoes which they place on the grid in turn. A player can place a domino either horizontally or vertically. Contrary to the related game of Domineering, the possible moves are the same for the two players, and Cram is then an impartial game.
As for all impartial games, there are two possible conventions for victory: in the normal game, the first player who cannot move loses, and on the contrary, in the misère version, the first player who cannot move wins.
Symmetry play
[edit]The winning strategy for normal Cram is simple for even-by-even boards and even-by-odd boards. In the even-by-even case, the second player wins by symmetry play. This means that for any move by Player 1, Player 2 has a corresponding symmetric move across the horizontal and vertical axes. In a sense, player 2 'mimics' the moves made by Player 1. If Player 2 follows this strategy, Player 2 will always make the last move, and thus win the game.
In the even-by-odd case, the first player wins by similar symmetry play. Player 1 places their first domino in the center two squares on the grid. Player 2 then makes their move, but Player 1 can play symmetrically thereafter, thus ensuring a win for Player 1.[2]
Symmetry play is a useless strategy in the misère version, because in that case it would only ensure the player that they lose.
Normal version
[edit]Grundy value
[edit]Since Cram is an impartial game, the Sprague–Grundy theorem indicates that in the normal version any Cram position is equivalent to a nim-heap of a given size, also called the Grundy value. Some values can be found in Winning Ways for your Mathematical Plays, in particular the 2 × n board, whose value is 0 if n is even and 1 if n is odd.
The symmetry strategy implies that even-by-even boards have a Grundy value of 0, but in the case of even-by-odd boards it only implies a Grundy value greater or equal to 1.
| n × m | 4 | 5 | 6 | 7 | 8 | 9 |
|---|---|---|---|---|---|---|
| 4 | 0 | 2 | 0 | 3 | 0 | 1 |
| 5 | - | 0 | 2 | 1 | 1 | 1 |
| 6 | - | - | 0 | 5 | 0 | 1 |
| 7 | - | - | - | 1 | 3 | 1 |
Known values
[edit]In 2009, Martin Schneider computed the Grundy values up to the 3 × 9, 4 × 5 and 5 × 7 boards.[3] In 2010, Julien Lemoine and Simon Viennot applied to the game of Cram algorithms that were initially developed for the game of Sprouts.[4] It allowed them to compute the Grundy values up to the 3 × 20, 4 × 9, 5 × 9, 6 × 7 and 7 × 7 boards.[5] Piotr Beling extended these results up to the 6 × 9, 7 × 8, and 7 × 9 boards.[6]
The sequence of currently known Grundy values for 3 × n boards, from n=1 to n=20 is: 1, 1, 0, 1, 1, 4, 1, 3, 1, 2, 0, 1, 2, 3, 1, 4, 0, 1, 0, 2. It doesn't appear to show any pattern.
The table below details the known results for boards with both dimensions greater than 3. Since the value of an n × m board is the same as the value of a m × n board, we give only the upper part of the table.
Misère version
[edit]Misère Grundy-value
[edit]The misère Grundy-value of a game G is defined by Conway in On Numbers and Games as the unique number n such that G+n is a second player win in misère play.[7] Even if it looks very similar to the usual Grundy-value in normal play, it is not as powerful. In particular, it is not possible to deduce the misère Grundy value of a sum of games only from their respective misère Grundy values.
| n × m | 4 | 5 | 6 | 7 | 8 | 9 |
|---|---|---|---|---|---|---|
| 4 | 0 | 0 | 0 | 1 | 1 | 1 |
| 5 | - | 2 | 1 | 1 | ? | ? |
| 6 | - | - | 1 | ? | ? | ? |
In 2009, Martin Schneider computed the misère grundy values up to the 3 × 9, 4 × 6, and 5 × 5 board.[3] In 2010, Julien Lemoine and Simon Viennot extended these results up to the 3 × 15, 4 × 9 and 5 × 7 boards, along with the value of the 6 × 6 board.[5]
The sequence of currently known misère Grundy values for 3 × n boards, from n=1 to n=15 is: 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 1. This sequence is conjectured to be periodic of period 3.[5]
The adjacent table details the known misère results for boards with both dimensions greater than 3.
References
[edit]- Berlekamp, Elwyn R.; Conway, John H.; Guy, Richard K. (2003). Winning Ways for Your Mathematical Plays. A K Peters, Ltd.
- ^ Gardner, Martin (1974). "Mathematical Games: Cram, crosscram and quadraphage: new games having elusive winning strategies". Scientific American. 230 (2): 106–108. doi:10.1038/scientificamerican0374-102.
- ^ Uiterwijk, Jos (December 2020). "Solving Cram Using Combinational Game Theory". ResearchGate.
- ^ a b Das Spiel Juvavum, Martin Schneider, Master thesis, 2009
- ^ Julien, Lemoine; Simon, Viennot (2010). "Nimbers are inevitable". arXiv:1011.5841 [math.CO].
- ^ a b c Computation records of normal and misère Cram, Julien Lemoine and Simon Viennot web site
- ^ Rust software for solving impartial games Piotr Beling
- ^ John H., Conway (2000). On Numbers and Games. A K Peters, Ltd.